package com.cheung.leetcode.normal;

import java.util.ArrayList;
import java.util.List;

public class LC22 {

    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        // 有效的括号，要保证任何适合左括号的数量都大于等于有括号的数量
        backtracking(n, "", result, 0, 0);
        return result;
    }

    private static void backtracking(int n, String path, List<String> result, int left, int right) {
        if (path.length() == 2 * n && left == right) {
            result.add(path);
        }

        if (left >= right) {

            String[] temp = {"(", ")"};
            for (String s : temp) {
                if ("(".equals(s) && left <= n) {
                    path += s;
                    left++;
                    backtracking(n, path, result, left, right);
                    path = path.substring(0, path.length() - 1);
                    left--;
                }
                if (")".equals(s) && right <= n) {
                    path += s;
                    right++;
                    backtracking(n, path, result, left, right);
                    path = path.substring(0, path.length() - 1);
                    right--;
                }
            }
        }


    }


    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }
}
